#ifndef ArvBinPesq_
#define ArvBinPesq_

#include "ArvBin.h"
#include "ArvBinNodo.h"

template<class T>
class ArvBinPesq: public ArvBin<T> {
private:

	ArvBinNodo<T>* pesquisar(const T & chave, ArvBinNodo<T>* rz) const;
	ArvBinNodo<T>* juntarno(const T & chave, ArvBinNodo<T>* rz);
	void eliminar(const T & chave, ArvBinNodo<T>* rz, ArvBinNodo<T>* ant);

public:

	void juntarno(const T &chave);
	bool pesquisar(T& chave) const;
	void eliminar(const T& chave);

};

template<class T>
void ArvBinPesq<T>::juntarno(const T & chave) {
	this->raiz = juntarno(chave, this->raiz);
}

template<class T>
ArvBinNodo<T> * ArvBinPesq<T>::juntarno(const T & chave, ArvBinNodo<T>* rz) {
	if (rz == NULL) {
		ArvBinNodo<T>* novoNo = new ArvBinNodo<T>(chave, NULL, NULL);
		rz = novoNo;
	} else if (*(rz->getInf()) == *chave)
		std::cout << "\nElemento repetido: " << *(chave) << std::endl;
	else if (*(rz->getInf()) > *chave)
		rz->setEsq(juntarno(chave, rz->getEsq()));
	else
		rz->setDir(juntarno(chave, rz->getDir()));
	return rz;
}

template<class T>
bool ArvBinPesq<T>::pesquisar(T & chave) const {
	ArvBinNodo<T>* temp = pesquisar(chave, this->raiz);

	if (temp != NULL) {
		if (temp->getInf() == chave)
			chave = temp->getInf();

		return true;
	} else
		return false;
}

template<class T>
ArvBinNodo<T>* ArvBinPesq<T>::pesquisar(const T & chave, ArvBinNodo<T>* rz) const {
	if (rz == NULL)
		return rz;
	else if (rz->getInf() == chave)
		return rz;
	else if (rz->getInf() > chave)
		return pesq_rec(chave, rz->getEsq());
	else
		return pesq_rec(chave, rz->getDir());
}

template<class T>
void ArvBinPesq<T>::eliminar(const T & chave) {
	ArvBinNodo<T>* ant = NULL;

	eliminar(chave, this->raiz, ant);
}

template<class T>
void ArvBinPesq<T>::eliminar(const T & chave, ArvBinNodo<T>* rz, ArvBinNodo<T>* ant) {
	if (rz != NULL)
		if (rz->getInf() < chave)
			eliminar(chave, rz->getDir(), rz);
		else if (rz->getInf() > chave)
			eliminar(chave, rz->getEsq(), rz);
		else if (rz->getEsq() == NULL) //Verifica se não tem subarv esq
		{
			if (ant == NULL) {
				this->raiz = rz->getDir();
				delete rz;
			} else {
				if (ant->getInf() < chave)
					ant->setDir(rz->getDir());
				else
					ant->setEsq(rz->getDir());
				delete rz;
			}
		} else // Encontrar o nó filho esq que está mais à dir
		{
			ArvBinNodo<T>* q, *p;

			q = rz->getEsq();
			p = q->getDir();
			if (p == NULL) {
				rz->setInf(q->getInf());
				rz->setEsq(q->getEsq());
				delete q;
			} else {
				while (p->getDir() != NULL) {
					q = p;
					p = p->getDir();
				}
				rz->setInf(p->getInf());
				q->setDir(p->getEsq());
				delete p;
			}
		}
	else
		std::cout << "Elem nao existe na arvore" << std::endl;
}

#endif
